{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Jump Game V"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxJumps"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #跳跃游戏 V"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组&nbsp;<code>arr</code> 和一个整数&nbsp;<code>d</code> 。每一步你可以从下标&nbsp;<code>i</code>&nbsp;跳到：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>i + x</code>&nbsp;，其中&nbsp;<code>i + x &lt; arr.length</code>&nbsp;且&nbsp;<code>0 &lt; x &lt;= d</code>&nbsp;。</li>\n",
    "\t<li><code>i - x</code>&nbsp;，其中&nbsp;<code>i - x &gt;= 0</code>&nbsp;且&nbsp;<code>0 &lt; x &lt;= d</code>&nbsp;。</li>\n",
    "</ul>\n",
    "\n",
    "<p>除此以外，你从下标&nbsp;<code>i</code> 跳到下标 <code>j</code>&nbsp;需要满足：<code>arr[i] &gt; arr[j]</code>&nbsp;且 <code>arr[i] &gt; arr[k]</code>&nbsp;，其中下标&nbsp;<code>k</code>&nbsp;是所有 <code>i</code>&nbsp;到 <code>j</code>&nbsp;之间的数字（更正式的，<code>min(i, j) &lt; k &lt; max(i, j)</code>）。</p>\n",
    "\n",
    "<p>你可以选择数组的任意下标开始跳跃。请你返回你 <strong>最多</strong>&nbsp;可以访问多少个下标。</p>\n",
    "\n",
    "<p>请注意，任何时刻你都不能跳到数组的外面。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/02/02/meta-chart.jpeg\" style=\"height: 419px; width: 633px;\"></p>\n",
    "\n",
    "<pre><strong>输入：</strong>arr = [6,4,14,6,8,13,9,7,10,6,12], d = 2\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>你可以从下标 10 出发，然后如上图依次经过 10 --&gt; 8 --&gt; 6 --&gt; 7 。\n",
    "注意，如果你从下标 6 开始，你只能跳到下标 7 处。你不能跳到下标 5 处因为 13 &gt; 9 。你也不能跳到下标 4 处，因为下标 5 在下标 4 和 6 之间且 13 &gt; 9 。\n",
    "类似的，你不能从下标 3 处跳到下标 2 或者下标 1 处。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>arr = [3,3,3,3,3], d = 3\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>你可以从任意下标处开始且你永远无法跳到任何其他坐标。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>arr = [7,6,5,4,3,2,1], d = 1\n",
    "<strong>输出：</strong>7\n",
    "<strong>解释：</strong>从下标 0 处开始，你可以按照数值从大到小，访问所有的下标。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>arr = [7,1,7,1,7,1], d = 2\n",
    "<strong>输出：</strong>2\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 5：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>arr = [66], d = 1\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= arr.length &lt;= 1000</code></li>\n",
    "\t<li><code>1 &lt;= arr[i] &lt;= 10^5</code></li>\n",
    "\t<li><code>1 &lt;= d &lt;= arr.length</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [jump-game-v](https://leetcode.cn/problems/jump-game-v/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [jump-game-v](https://leetcode.cn/problems/jump-game-v/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[6,4,14,6,8,13,9,7,10,6,12]\\n2', '[3,3,3,3,3]\\n3', '[7,6,5,4,3,2,1]\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJumps(self, arr: List[int], d: int) -> int:\n",
    "        check_flag = [0] * len(arr)\n",
    "        flag = 0\n",
    "        dp = [1]*len(arr)\n",
    "\n",
    "        while flag < len(arr):\n",
    "            for i in range(len(arr)):\n",
    "                if check_flag[i] == 1:\n",
    "                    continue\n",
    "                \n",
    "                left = max(0,i-d)\n",
    "                right = min(len(arr)-1 , i+d)\n",
    "                leap_able = 0\n",
    "                for j in range(i-1,left-1,-1):\n",
    "                    if arr[j]>= arr[i]:\n",
    "                        break\n",
    "                    if leap_able == 0 and check_flag[j] == 0:\n",
    "                        leap_able = 1\n",
    "                        break\n",
    "                    dp[i] = max(dp[i],1+dp[j])\n",
    "                for j in range(i+1,right+1):\n",
    "                    if arr[j]>= arr[i]:\n",
    "                        break\n",
    "                    if leap_able == 0 and check_flag[j] == 0:\n",
    "                        leap_able = 1\n",
    "                        break\n",
    "                    dp[i] = max(dp[i],1+dp[j])\n",
    "                if leap_able == 0:\n",
    "                    check_flag[i] = 1\n",
    "                    flag = flag + 1\n",
    "        return max(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJumps(self, arr: List[int], d: int) -> int:\n",
    "        n = len(arr)\n",
    "        dp = [1] * n\n",
    "        ans = 1\n",
    "        for i in sorted(list(range(n)), key=lambda x: arr[x]):\n",
    "            k = 1\n",
    "            while k <= d and i - k >= 0 and arr[i] > arr[i-k]:\n",
    "                dp[i] = max(dp[i], dp[i-k] + 1)\n",
    "                k += 1\n",
    "            k = 1\n",
    "            while k <= d and i + k < n and arr[i] > arr[i+k]:\n",
    "                dp[i] = max(dp[i], dp[i+k] + 1)\n",
    "                k += 1\n",
    "            ans = max(dp[i], ans)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJumps(self, arr: List[int], d: int) -> int:\n",
    "        n = len(arr)\n",
    "        newList = [(arr[i], i) for i in range(n)]\n",
    "        newList.sort(key=lambda x: x[0])\n",
    "\n",
    "        dp = [1] * n\n",
    "\n",
    "        for node in newList:\n",
    "            cur_h, cur_index = node\n",
    "            cur_visit = 1\n",
    "\n",
    "            for next_index in range(cur_index-1, max(0, cur_index-d)-1, -1):\n",
    "                if arr[next_index] >= cur_h:\n",
    "                    break\n",
    "                cur_visit = max(dp[next_index]+1, cur_visit)\n",
    "            \n",
    "            for next_index in range(cur_index+1, min(n, cur_index+d+1)):\n",
    "                if arr[next_index] >= cur_h:\n",
    "                    break\n",
    "                cur_visit = max(dp[next_index]+1, cur_visit)\n",
    "            \n",
    "            dp[cur_index] = cur_visit\n",
    "        \n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJumps(self, arr: List[int], d: int) -> int:\n",
    "        n = len(arr)\n",
    "        dp = [1] * n\n",
    "        ans = 1\n",
    "        for i in sorted(list(range(n)), key=lambda x: arr[x]):\n",
    "            for j in range(i-1, max(-1, i-d-1), -1):\n",
    "                if arr[i] <= arr[j]:\n",
    "                    break\n",
    "                dp[i] = max(dp[i], dp[j] + 1)\n",
    "            for j in range(i+1, min(i+d+1, n)):\n",
    "                if arr[i] <= arr[j]:\n",
    "                    break\n",
    "                dp[i] = max(dp[i], dp[j] + 1)\n",
    "            ans = max(dp[i], ans)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxJumps(self, arr: List[int], d: int) -> int:\n",
    "        n = len(arr)\n",
    "        arr2 = [(arr[i], i) for i in range(n)]\n",
    "        arr2 = sorted(arr2, key=lambda x: x[0])\n",
    "\n",
    "        dp = [1] * n\n",
    "        for h, i in arr2:\n",
    "            cur = 1  # 可跳跃的数量\n",
    "            for l in range(i - 1, max(0, i - d) - 1, -1):\n",
    "                if arr[l] >= h:\n",
    "                    break\n",
    "                cur = max(cur, dp[l] + 1)\n",
    "\n",
    "            for r in range(i + 1, min(n, i + d + 1)):\n",
    "                if arr[r] >= h:\n",
    "                    break\n",
    "                cur = max(cur, dp[r] + 1)\n",
    "            dp[i] = cur\n",
    "        return max(dp)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJumps(self, arr: List[int], d: int) -> int:\n",
    "        num_idx = []\n",
    "        for i, num in enumerate(arr):\n",
    "            num_idx.append((num, i))\n",
    "        \n",
    "        num_idx.sort()\n",
    "        n = len(arr)\n",
    "        f = [1] * n\n",
    "\n",
    "        for i in range(n):\n",
    "            # 最开始计算的位置的索引和值\n",
    "            num, idx = num_idx[i]\n",
    "            minidx = max(0, idx - d)\n",
    "            maxidx = min(idx + d, n-1)\n",
    "            for left in range(idx-1, minidx -1, -1):\n",
    "                if arr[left] < num:\n",
    "                    f[idx] = max(f[idx], f[left] + 1)\n",
    "                else:\n",
    "                    break\n",
    "            for right in range(idx+1, maxidx + 1):\n",
    "                if arr[right] < num:\n",
    "                    f[idx] = max(f[idx], f[right] + 1)\n",
    "                else:\n",
    "                    break\n",
    "\n",
    "        return max(f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJumps(self, arr: List[int], d: int) -> int:\n",
    "        n = len(arr)\n",
    "        L = sorted([(h, i) for i, h in enumerate(arr)], key=lambda x:x[0])\n",
    "        dp = [1] * n\n",
    "        for h, i in L:\n",
    "            cur = 1\n",
    "            for j in range(i-1, max(0, i-d)-1, -1):\n",
    "                if arr[j] >= arr[i]:\n",
    "                    break\n",
    "                cur = max(cur, dp[j] + 1)\n",
    "            for j in range(i+1, min(n, i+d+1)):\n",
    "                if arr[j] >= arr[i]:\n",
    "                    break\n",
    "                cur = max(cur, dp[j] + 1)\n",
    "            dp[i] = cur\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJumps(self, arr: List[int], d: int) -> int:\n",
    "        n = len(arr)\n",
    "        L = [(arr[i],i) for i in range(n)]\n",
    "        L.sort(key = lambda x: x[0])\n",
    "        dp = [1]*n\n",
    "        for h,i in L:\n",
    "            cur = 1\n",
    "            for idx in range(i-1,max(0,i-d)-1,-1):\n",
    "                if arr[idx] >= h:\n",
    "                    break\n",
    "                cur = max(dp[idx]+1,cur)\n",
    "            for idx in range(i+1,min(n,i+d+1)):\n",
    "                if arr[idx] >= h:\n",
    "                    break\n",
    "                cur = max(dp[idx]+1,cur)\n",
    "            dp[i] = cur\n",
    "        return max(dp)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJumps(self, arr: List[int], d: int) -> int:\n",
    "        nums = [(num, i) for i, num in enumerate(arr)]\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "\n",
    "        f = [1] * n\n",
    "\n",
    "        # 枚举的是nums中的数字\n",
    "        for i in range(1, n):\n",
    "            num, idx = nums[i][0], nums[i][1]\n",
    "            minidx, maxidx = max(0, idx - d), min(idx + d, n-1)\n",
    "            \n",
    "            left = idx - 1\n",
    "            while left >= minidx and arr[left] < num:\n",
    "                f[idx] = max(f[idx], f[left] + 1)\n",
    "                left -= 1\n",
    "            \n",
    "            right = idx + 1\n",
    "            while right <= maxidx and arr[right] < num:\n",
    "                f[idx] = max(f[idx], f[right] + 1)\n",
    "                right += 1\n",
    "            \n",
    "        return max(f)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJumps(self, arr: List[int], d: int) -> int:\n",
    "        n = len(arr)\n",
    "        L = [(arr[i],i) for i in range(n)]\n",
    "        L.sort(key = lambda x: x[0])\n",
    "        dp = [1]*n\n",
    "        for h,i in L:\n",
    "            cur = 1\n",
    "            for idx in range(i-1,max(0,i-d)-1,-1):\n",
    "                if arr[idx] >= h:\n",
    "                    break\n",
    "                cur = max(dp[idx]+1,cur)\n",
    "            for idx in range(i+1,min(n,i+d+1)):\n",
    "                if arr[idx] >= h:\n",
    "                    break\n",
    "                cur = max(dp[idx]+1,cur)\n",
    "            dp[i] = cur\n",
    "        return max(dp)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJumps(self, arr: List[int], d: int) -> int:\n",
    "        n = len(arr)\n",
    "        p = [0] * n\n",
    "        \n",
    "        for v, i in sorted(zip(arr, list(range(n)))):\n",
    "            for j in range(1, d+1):\n",
    "                if i + j < n and arr[i] > arr[i + j]:\n",
    "                    p[i] = max(p[i], p[i + j])\n",
    "                else:\n",
    "                    break\n",
    "            for j in range(1, d+1):    \n",
    "                if i - j >= 0 and arr[i] > arr[i - j]:\n",
    "                    p[i] = max(p[i], p[i - j])\n",
    "                else:\n",
    "                    break\n",
    "            p[i] += 1\n",
    "        return max(p)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJumps(self, arr: List[int], d: int) -> int:\n",
    "        nm=len(arr)\n",
    "        nums=arr\n",
    "        ll, rr, stack = [-1] * nm, [nm] * nm, []\n",
    "        for i in range(nm):\n",
    "            while stack and nums[stack[-1]] <= nums[i]:  # 这里找的是左边第一个大于等于自身的数字的位置，如果是小于则加上=\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                ll[i] = stack[-1]\n",
    "            stack.append(i)\n",
    "        stack = []\n",
    "        for i in range(nm - 1, -1, -1):\n",
    "            while stack and nums[stack[-1]] <= nums[i]:  # 这里找的是右边第一个大于自身的数字的位置， 如果是小于等于则去掉=\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                rr[i] = stack[-1]\n",
    "            stack.append(i)\n",
    "\n",
    "\n",
    "        dp=[1 for i in range(nm)]\n",
    "        for num, i in sorted(zip(nums, range(nm)), reverse=False):\n",
    "#            print(num,i)\n",
    "            if i-ll[i]<=d and ll[i]>=0: dp[ll[i]]=max(dp[ll[i]],dp[i]+1)\n",
    "            if rr[i]-i<=d and rr[i]<nm: dp[rr[i]] = max(dp[rr[i]],dp[i] + 1)\n",
    "\n",
    "\n",
    "        #print(dp)\n",
    "        return max(dp)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxJumps(self, arr: List[int], d: int) -> int:\n",
    "        n = len(arr)\n",
    "        arr2 = [(arr[i], i) for i in range(n)]\n",
    "        arr2 = sorted(arr2, key=lambda x: x[0])\n",
    "\n",
    "        dp = [0] * n\n",
    "        for h, i in arr2:\n",
    "            cur = 1\n",
    "            for l in range(i - 1, max(0, i - d) - 1, -1):\n",
    "                if arr[l] >= h:\n",
    "                    break\n",
    "                cur = max(cur, dp[l] + 1)\n",
    "\n",
    "            for r in range(i + 1, min(n, i + d + 1)):\n",
    "                if arr[r] >= h:\n",
    "                    break\n",
    "                cur = max(cur, dp[r] + 1)\n",
    "            dp[i] = cur\n",
    "        return max(dp)\n",
    "\n",
    "\n",
    "# dp\n",
    "# 我们记录每个下标 i 可以最多访问的下标个数，返回最大值就行了。\n",
    "# 如何记录每个下标的最多访问个数呢？我们使用一维动态规划数组 dp 。\n",
    "# dp[i] 表示下标 i 的最多可访问次数，我们按照高度从低到高的顺序遍历每个下标，在可跳范围内，我们更新 dp[i] 的值。\n",
    "# 状态方程为 dp[i]=max(dp[idx]+1,cur)\n",
    "# class Solution:\n",
    "#     def maxJumps(self, arr: List[int], d: int) -> int:\n",
    "#         n = len(arr)\n",
    "#         arr2 = [(arr[i], i) for i in range(n)]\n",
    "#         arr2 = sorted(arr2, key=lambda x: x[0])\n",
    "\n",
    "#         dp = [1] * n\n",
    "#         for h, i in arr2:\n",
    "#             cur = 1  # 可跳跃的数量\n",
    "#             # 向左跳\n",
    "#             for l in range(i - 1, max(0, i - d) - 1, -1):\n",
    "#                 if arr[l] >= h:\n",
    "#                     break\n",
    "#                 cur = max(cur, dp[l] + 1)\n",
    "\n",
    "#             # 向右跳\n",
    "#             for r in range(i + 1, min(n, i + d + 1)):\n",
    "#                 if arr[r] >= h:\n",
    "#                     break\n",
    "#                 cur = max(cur, dp[r] + 1)\n",
    "#             dp[i] = cur\n",
    "#         return max(dp)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJumps(self, arr: List[int], d: int) -> int:\n",
    "        test = []\n",
    "        for i in range(len(arr)):\n",
    "            test.append([arr[i], i])\n",
    "        test.sort(reverse=True)\n",
    "        dp = [1 for i in range(len(arr))]\n",
    "        for i, j in test:\n",
    "            for r in range(j - 1, max(j - d - 1, -1), -1):\n",
    "                if arr[r] < i:\n",
    "                    dp[r] = max(dp[r], dp[j] + 1)\n",
    "                else:\n",
    "                    break\n",
    "            for r in range(j + 1, min(j + d + 1, len(arr))):\n",
    "                if arr[r] < i:\n",
    "                    dp[r] = max(dp[r], dp[j] + 1)\n",
    "                else:\n",
    "                    break\n",
    "        return max(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJumps(self, arr: List[int], d: int) -> int:\n",
    "        nm=len(arr)\n",
    "        nums=arr\n",
    "        ll, rr, stack = [-1] * nm, [nm] * nm, []\n",
    "        for i in range(nm):\n",
    "            while stack and nums[stack[-1]] <= nums[i]:  # 这里找的是左边第一个小于等于自身的数字的位置，如果是小于则加上=\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                ll[i] = stack[-1]\n",
    "            stack.append(i)\n",
    "\n",
    "        stack = []\n",
    "        for i in range(nm - 1, -1, -1):\n",
    "            while stack and nums[stack[-1]] <= nums[i]:  # 这里找的是右边第一个小于自身的数字的位置， 如果是小于等于则去掉=\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                rr[i] = stack[-1]\n",
    "            stack.append(i)\n",
    "\n",
    "        #print(ll)\n",
    "        #print(rr)\n",
    "\n",
    "        dp=[1 for i in range(nm)]\n",
    "        for num, i in sorted(zip(nums, range(nm)), reverse=False):\n",
    "#            print(num,i)\n",
    "            if i-ll[i]<=d and ll[i]>=0: dp[ll[i]]=max(dp[ll[i]],dp[i]+1)\n",
    "            if rr[i]-i<=d and rr[i]<nm: dp[rr[i]] = max(dp[rr[i]],dp[i] + 1)\n",
    "\n",
    "#        print(dp)\n",
    "        return max(dp)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJumps(self, arr: List[int], d: int) -> int:\n",
    "        nm=len(arr)\n",
    "        nums=arr\n",
    "        ll, rr, stack = [-1] * nm, [nm] * nm, []\n",
    "        for i in range(nm):\n",
    "            while stack and nums[stack[-1]] <= nums[i]:  # 这里找的是左边第一个大于等于自身的数字的位置，如果是小于则加上=\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                ll[i] = stack[-1]\n",
    "            stack.append(i)\n",
    "        stack = []\n",
    "        for i in range(nm - 1, -1, -1):\n",
    "            while stack and nums[stack[-1]] <= nums[i]:  # 这里找的是右边第一个大于自身的数字的位置， 如果是小于等于则去掉=\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                rr[i] = stack[-1]\n",
    "            stack.append(i)\n",
    "\n",
    "\n",
    "        dp=[1 for i in range(nm)]\n",
    "        for num, i in sorted(zip(nums, range(nm)), reverse=False):\n",
    "#            print(num,i)\n",
    "            if i-ll[i]<=d and ll[i]>=0: dp[ll[i]]=max(dp[ll[i]],dp[i]+1)\n",
    "            if rr[i]-i<=d and rr[i]<nm: dp[rr[i]] = max(dp[rr[i]],dp[i] + 1)\n",
    "\n",
    "\n",
    "        #print(dp)\n",
    "        return max(dp)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJumps(self, arr: List[int], d: int) -> int:\n",
    "        id = sorted(range(len(arr)), key=lambda k: arr[k])\n",
    "        dp = [1] * len(arr)\n",
    "        for pos in id:\n",
    "            i = pos - 1\n",
    "            while i >= 0 and pos - i <= d and arr[pos] > arr[i]:\n",
    "                dp[pos] = max(dp[pos], dp[i] + 1)\n",
    "                i -= 1\n",
    "            i = pos + 1\n",
    "            while i < len(arr) and i - pos <= d and arr[pos] > arr[i]:\n",
    "                dp[pos] = max(dp[pos], dp[i] + 1)\n",
    "                i += 1\n",
    "        print(dp)\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def maxJumps(self, arr: List[int], d: int) -> int:\r\n",
    "        n = len(arr)\r\n",
    "        dp = [0] * n\r\n",
    "        a = sorted([(i, arr[i]) for i in range(n)], key=lambda x: x[1])  # 按高度排序\r\n",
    "\r\n",
    "        for i in range(n):\r\n",
    "            cur = a[i][0]  # 当前dp的索引\r\n",
    "            L = cur - 1 if cur >= 1 else 0  # 左边界L初始为cur-1位置, 如果小于0,取0\r\n",
    "            R = cur + 1 if cur <= n - 2 else n - 1  # 右边界R初始为cur+1,如果大于n-1,就取 n-1.\r\n",
    "\r\n",
    "            while 0 <= L:  # 寻找左边界\r\n",
    "                if arr[L] >= a[i][1]:  # 如果高度超过了当前的,即跳不过.\r\n",
    "                    L += 1  # 往回一步,\r\n",
    "                    if L > cur: L = cur  # 检查左边界是否越过当前\r\n",
    "                    break  # 跳出\r\n",
    "                L -= 1\r\n",
    "                if L < 0:  # 检查是否小于0\r\n",
    "                    L = 0\r\n",
    "                    break\r\n",
    "                if L < cur - d:  # 检查是否超过 d 步数\r\n",
    "                    L += 1  # 如果超过了,就要回退1步.\r\n",
    "                    break\r\n",
    "\r\n",
    "            while R < n:  #寻找右边界\r\n",
    "                if arr[R] >= a[i][1]:  # 右边界如果超过高度,跳不过了.\r\n",
    "                    R -= 1  # 回退一步.\r\n",
    "                    if R < cur: R = cur  # 检查是否越过了cur,\r\n",
    "                    break\r\n",
    "                R += 1\r\n",
    "                if R > n - 1:  # 是否越过数组边界\r\n",
    "                    R = n - 1\r\n",
    "                    break\r\n",
    "                if R > cur + d:  # 是否超过了 d 步数\r\n",
    "                    R -= 1\r\n",
    "                    break\r\n",
    "\r\n",
    "            dp[cur] = max(dp[L:R + 1]) + 1  # 即左右能跳最多的步数 + 当前位置的1.\r\n",
    "\r\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def maxJumps(self, arr: [], d: int):\n",
    "        nm=len(arr)\n",
    "        nums=arr\n",
    "        ll, rr, stack = [-1] * nm, [nm] * nm, []\n",
    "        for i in range(nm):\n",
    "            while stack and nums[stack[-1]] <= nums[i]:  # 这里找的是左边第一个小于等于自身的数字的位置，如果是小于则加上=\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                ll[i] = stack[-1]\n",
    "            stack.append(i)\n",
    "\n",
    "        stack = []\n",
    "        for i in range(nm - 1, -1, -1):\n",
    "            while stack and nums[stack[-1]] <= nums[i]:  # 这里找的是右边第一个小于自身的数字的位置， 如果是小于等于则去掉=\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                rr[i] = stack[-1]\n",
    "            stack.append(i)\n",
    "\n",
    "        print(ll)\n",
    "        print(rr)\n",
    "\n",
    "        dp=[1 for i in range(nm)]\n",
    "        for num, i in sorted(zip(nums, range(nm)), reverse=False):\n",
    "#            print(num,i)\n",
    "            if i-ll[i]<=d and ll[i]>=0: dp[ll[i]]=max(dp[ll[i]],dp[i]+1)\n",
    "            if rr[i]-i<=d and rr[i]<nm: dp[rr[i]] = max(dp[rr[i]],dp[i] + 1)\n",
    "\n",
    "#        print(dp)\n",
    "        return max(dp)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class RangeAscendRangeMax:\n",
    "    # 模板：线段树区间更新、持续增加最大值\n",
    "    def __init__(self, n):\n",
    "        self.n = n\n",
    "        self.cover = [-inf] * (4 * n)\n",
    "        self.lazy = [-inf] * (4 * n)\n",
    "\n",
    "    @staticmethod\n",
    "    def _max(a, b):\n",
    "        return a if a > b else b\n",
    "    \n",
    "    def _make_tag(self, i, val) -> None:\n",
    "        self.cover[i] = self._max(self.cover[i], val)\n",
    "        self.lazy[i] = self._max(self.lazy[i], val)\n",
    "        return\n",
    "    \n",
    "    def _push_up(self, i):\n",
    "        self.cover[i] = self._max(self.cover[2 * i], self.cover[2 * i + 1])\n",
    "        return\n",
    "\n",
    "    def _push_down(self, i):\n",
    "        # 懒标记下放，注意取最大值\n",
    "        if self.lazy[i] != -inf:\n",
    "            self.cover[2 * i] = self._max(self.cover[2 * i], self.lazy[i])\n",
    "            self.cover[2 * i + 1] = self._max(self.cover[2 * i + 1], self.lazy[i])\n",
    "            self.lazy[2 * i] = self._max(self.lazy[2 * i], self.lazy[i])\n",
    "            self.lazy[2 * i + 1] = self._max(self.lazy[2 * i + 1], self.lazy[i])\n",
    "            self.lazy[i] = -inf\n",
    "        return\n",
    "\n",
    "    def build(self, nums: List[int]) -> None:\n",
    "        # 使用数组初始化线段树\n",
    "        assert self.n == len(nums)\n",
    "        stack = [[0, self.n - 1, 1]]\n",
    "        while stack:\n",
    "            s, t, ind = stack.pop()\n",
    "            if ind >= 0:\n",
    "                if s == t:\n",
    "                    self._make_tag(ind, nums[s])\n",
    "                else:\n",
    "                    stack.append([s, t, ~ind])\n",
    "                    m = s + (t - s) // 2\n",
    "                    stack.append([s, m, 2 * ind])\n",
    "                    stack.append([m + 1, t, 2 * ind + 1])\n",
    "            else:\n",
    "                ind = ~ind\n",
    "                self._push_up(ind)\n",
    "        return\n",
    "    \n",
    "    def get(self):\n",
    "        # 查询区间的所有值\n",
    "        stack = [[0, self.n - 1, 1]]\n",
    "        nums = [0] * self.n\n",
    "        while stack:\n",
    "            s, t, i = stack.pop()\n",
    "            if s == t:\n",
    "                nums[s] = self.cover[i]\n",
    "                continue\n",
    "            m = s + (t - s) // 2\n",
    "            self._push_down(i)\n",
    "            stack.append([s, m, 2 * i])\n",
    "            stack.append([m + 1, t, 2 * i + 1])\n",
    "        return nums\n",
    "    \n",
    "    def range_ascend(self, left, right, val):\n",
    "        # 更新区间最大值\n",
    "        stack = [[0, self.n - 1, 1]]\n",
    "        while stack:\n",
    "            a, b, i = stack.pop()\n",
    "            if i >= 0:\n",
    "                if left <= a and b <= right:\n",
    "                    self._make_tag(i, val)\n",
    "                    continue\n",
    "                self._push_down(i)\n",
    "                stack.append([a, b, ~i])\n",
    "                m = a + (b - a) // 2\n",
    "                if left <= m: \n",
    "                    stack.append([a, m, 2 * i])\n",
    "                if right > m:\n",
    "                    stack.append([m + 1, b, 2 * i + 1])\n",
    "            else:\n",
    "                i = ~i\n",
    "                self._push_up(i)\n",
    "        return\n",
    "\n",
    "    def range_max(self, left, right):\n",
    "        # 查询区间的最大值\n",
    "        stack = [[0, self.n - 1, 1]]\n",
    "        highest = -inf\n",
    "        while stack:\n",
    "            a, b, i = stack.pop()\n",
    "            if left <= a and b <= right:\n",
    "                highest = self._max(highest, self.cover[i])\n",
    "                continue\n",
    "            self._push_down(i)\n",
    "            m = a + (b - a) // 2\n",
    "            if left <= m:\n",
    "                stack.append([a, m, 2 * i])\n",
    "            if right > m:\n",
    "                stack.append([m + 1, b, 2 * i + 1])\n",
    "        return highest\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxJumps(self, nums: List[int], d: int) -> int:\n",
    "    # 模板：可以使用线段树DP进行解决\n",
    "        n = len(nums)\n",
    "        post = [n - 1] * n\n",
    "        stack = []\n",
    "        for i in range(n):\n",
    "            while stack and nums[stack[-1]] <= nums[i]:\n",
    "                post[stack.pop()] = i - 1\n",
    "            stack.append(i)\n",
    "\n",
    "        pre = [0] * n\n",
    "        stack = []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while stack and nums[stack[-1]] <= nums[i]:\n",
    "                pre[stack.pop()] = i + 1\n",
    "            stack.append(i)\n",
    "\n",
    "        # 分桶排序转移\n",
    "        dct = defaultdict(list)\n",
    "        for i, num in enumerate(nums):\n",
    "            dct[num].append(i)\n",
    "        tree = RangeAscendRangeMax(n)\n",
    "        tree.build([0]*n)\n",
    "        for num in sorted(dct):\n",
    "            cur = []\n",
    "            for i in dct[num]:\n",
    "                left, right = pre[i], post[i]\n",
    "                if left < i - d:\n",
    "                    left = i - d\n",
    "                if right > i + d:\n",
    "                    right = i + d\n",
    "                x = tree.range_max(left, right)\n",
    "                cur.append([x + 1, i])\n",
    "\n",
    "            for x, i in cur:\n",
    "                tree.range_ascend(i, i, x)\n",
    "        return tree.range_max(0, n - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def maxJumps(self, arr: List[int], d: int) -> int:\r\n",
    "        possibleplace=[]\r\n",
    "        for i in range(len(arr)):\r\n",
    "            possibleplace.append([])\r\n",
    "            L=i-1\r\n",
    "            while L>=max(0,i-d) and arr[L]<arr[i]:\r\n",
    "                L-=1\r\n",
    "            L+=1\r\n",
    "            possibleplace[i].append(L)\r\n",
    "            R=i+1\r\n",
    "            while R<=min(len(arr)-1,i+d) and arr[R]<arr[i]:\r\n",
    "                R+=1\r\n",
    "            R-=1\r\n",
    "            possibleplace[i].append(R) \r\n",
    "        dp=[0]*len(arr)\r\n",
    "        sortedarr=sorted([i for i in range(len(arr))],key=lambda x:arr[x])\r\n",
    "        for i in range(len(arr)):\r\n",
    "            index=sortedarr[i]\r\n",
    "            L,R=possibleplace[index]\r\n",
    "            if L!=index:\r\n",
    "                dp[index]=max(dp[L:index])+1\r\n",
    "            if R!=index:\r\n",
    "                dp[index]=max(dp[index],max(dp[index+1:R+1])+1)\r\n",
    "        print(sortedarr,dp,possibleplace)\r\n",
    "        return max(dp)+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJumps(self, arr: List[int], d: int) -> int:\n",
    "        nm=len(arr)\n",
    "        nums=arr\n",
    "        ll, rr, stack = [-1] * nm, [nm] * nm, []\n",
    "        for i in range(nm):\n",
    "            while stack and nums[stack[-1]] <= nums[i]:  # 这里找的是左边第一个小于等于自身的数字的位置，如果是小于则加上=\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                ll[i] = stack[-1]\n",
    "            stack.append(i)\n",
    "\n",
    "        stack = []\n",
    "        for i in range(nm - 1, -1, -1):\n",
    "            while stack and nums[stack[-1]] <= nums[i]:  # 这里找的是右边第一个小于自身的数字的位置， 如果是小于等于则去掉=\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                rr[i] = stack[-1]\n",
    "            stack.append(i)\n",
    "\n",
    "        print(ll)\n",
    "        print(rr)\n",
    "\n",
    "        dp=[1 for i in range(nm)]\n",
    "        for num, i in sorted(zip(nums, range(nm)), reverse=False):\n",
    "#            print(num,i)\n",
    "            if i-ll[i]<=d and ll[i]>=0: dp[ll[i]]=max(dp[ll[i]],dp[i]+1)\n",
    "            if rr[i]-i<=d and rr[i]<nm: dp[rr[i]] = max(dp[rr[i]],dp[i] + 1)\n",
    "\n",
    "#        print(dp)\n",
    "        return max(dp)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def maxJumps(self, arr: List[int], d: int) -> int:\r\n",
    "        possibleplace=[]\r\n",
    "        for i in range(len(arr)):\r\n",
    "            possibleplace.append([])\r\n",
    "            L=i-1\r\n",
    "            while L>=max(0,i-d) and arr[L]<arr[i]:\r\n",
    "                L-=1\r\n",
    "            L+=1\r\n",
    "            possibleplace[i].append(L)\r\n",
    "            R=i+1\r\n",
    "            while R<=min(len(arr)-1,i+d) and arr[R]<arr[i]:\r\n",
    "                R+=1\r\n",
    "            R-=1\r\n",
    "            possibleplace[i].append(R) \r\n",
    "        dp=[0]*len(arr)\r\n",
    "        sortedarr=sorted([i for i in range(len(arr))],key=lambda x:arr[x])\r\n",
    "        for i in range(len(arr)):\r\n",
    "            index=sortedarr[i]\r\n",
    "            L,R=possibleplace[index]\r\n",
    "            if L!=index:\r\n",
    "                dp[index]=max(dp[L:index])+1\r\n",
    "            if R!=index:\r\n",
    "                dp[index]=max(dp[index],max(dp[index+1:R+1])+1)\r\n",
    "        print(sortedarr,dp,possibleplace)\r\n",
    "        return max(dp)+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJumps(self, arr: List[int], d: int) -> int:\n",
    "        H = [ (h, i) for i, h in enumerate(arr) ]\n",
    "        H = sorted(H, key = lambda x : (x[0], x[1]) )\n",
    "        n = len(arr)\n",
    "        dp = [ 1 ] * n\n",
    "        ans = 0\n",
    "        for i, (h, idx) in enumerate(H):\n",
    "            if i == 0:\n",
    "                dp[idx] = 1\n",
    "            else:\n",
    "                left = max(idx-d, 0)\n",
    "                right = min(idx+d+1, n)\n",
    "                for j in range(idx - 1, left - 1, -1):\n",
    "                    if arr[j] < h:\n",
    "                        dp[idx] = max(dp[idx], dp[j] + 1)\n",
    "                    else:\n",
    "                        break\n",
    "                for j in range(idx + 1, right):\n",
    "                    if arr[j] < h:\n",
    "                        dp[idx] = max(dp[idx], dp[j] + 1)\n",
    "                    else:\n",
    "                        break\n",
    "            ans = max(ans, dp[idx])\n",
    "        print(dp)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJumps(self, arr: List[int], d: int) -> int:\n",
    "        nm=len(arr)\n",
    "        nums=arr\n",
    "        ll, rr, stack = [-1] * nm, [nm] * nm, []\n",
    "        for i in range(nm):\n",
    "            while stack and nums[stack[-1]] <= nums[i]:  # 这里找的是左边第一个小于等于自身的数字的位置，如果是小于则加上=\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                ll[i] = stack[-1]\n",
    "            stack.append(i)\n",
    "\n",
    "        stack = []\n",
    "        for i in range(nm - 1, -1, -1):\n",
    "            while stack and nums[stack[-1]] <= nums[i]:  # 这里找的是右边第一个小于自身的数字的位置， 如果是小于等于则去掉=\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                rr[i] = stack[-1]\n",
    "            stack.append(i)\n",
    "\n",
    "        print(ll)\n",
    "        print(rr)\n",
    "\n",
    "        dp=[1 for i in range(nm)]\n",
    "        for num, i in sorted(zip(nums, range(nm)), reverse=False):\n",
    "#            print(num,i)\n",
    "            if i-ll[i]<=d and ll[i]>=0: dp[ll[i]]=max(dp[ll[i]],dp[i]+1)\n",
    "            if rr[i]-i<=d and rr[i]<nm: dp[rr[i]] = max(dp[rr[i]],dp[i] + 1)\n",
    "\n",
    "#        print(dp)\n",
    "        return max(dp)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJumps(self, arr: List[int], d: int) -> int:\n",
    "        def solve(arr, d, pos):\n",
    "            if dp[pos]!= -1:\n",
    "                return dp[pos]\n",
    "            dp[pos] = 0\n",
    "            for k in range(1,d+1,1):\n",
    "                nxt = pos + k  \n",
    "                if nxt >= n or arr[pos] <= arr[nxt]:\n",
    "                    break\n",
    "                dp[pos] = max(dp[pos], 1+ solve(arr, d, nxt))\n",
    "            for k in range(1,d+1,1):\n",
    "                nxt = pos - k  \n",
    "                if nxt < 0 or arr[pos] <= arr[nxt]:\n",
    "                    break\n",
    "                dp[pos] = max(dp[pos],1+ solve(arr, d, nxt))\n",
    "            dp[pos] = max(dp[pos], 1)\n",
    "            return dp[pos]\n",
    "            \n",
    "        if not arr:\n",
    "            return 0 \n",
    "        n = len(arr)\n",
    "        dp = [-1] * n \n",
    "        ans = 1\n",
    "        for i in range(n):\n",
    "            if dp[i] == -1:\n",
    "                ans = max(ans, solve(arr,d, i))\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJumps(self, arr: List[int], d: int) -> int:\n",
    "        dp = [0]*len(arr)\n",
    "\n",
    "        def woo(i):\n",
    "            if dp[i]>0:\n",
    "                return dp[i]\n",
    "\n",
    "            dp[i] = 1\n",
    "            for di in (-1, 1):\n",
    "                for j in range(i+di, i+di*d+di, di):\n",
    "                    if j<0 or j>=len(arr) or arr[j]>=arr[i]:\n",
    "                        break\n",
    "\n",
    "                    dp[i] = max(dp[i], woo(j)+1)\n",
    "\n",
    "            return dp[i]\n",
    "\n",
    "        for i in range(len(arr)):\n",
    "            woo(i)\n",
    "\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJumps(self, arr: List[int], d: int) -> int:\n",
    "        dp = [0]*len(arr)\n",
    "\n",
    "        def woo(i):\n",
    "            if dp[i]>0:\n",
    "                return dp[i]\n",
    "\n",
    "            dp[i] = 1\n",
    "            for di in -1, 1:\n",
    "                for j in range(i+di, i+di*d+di, di):\n",
    "                    if j<0 or j>=len(arr) or arr[j]>=arr[i]:\n",
    "                        break\n",
    "\n",
    "                    dp[i] = max(dp[i], woo(j)+1)\n",
    "\n",
    "            return dp[i]\n",
    "\n",
    "        for i in range(len(arr)):\n",
    "            woo(i)\n",
    "\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJumps(self, arr: List[int], d: int) -> int:\n",
    "        dp = [0]*len(arr)\n",
    "\n",
    "        def woo(i):\n",
    "            if dp[i]>0:\n",
    "                return dp[i]\n",
    "\n",
    "            dp[i] = 1\n",
    "            for di in (-1, 1):\n",
    "                for j in range(i+di, i+d*di+di, di):\n",
    "                    if j<0 or j>=len(arr) or arr[j]>=arr[i]:\n",
    "                        break\n",
    "\n",
    "                    dp[i] = max(dp[i], woo(j)+1)\n",
    "            \n",
    "            return dp[i]\n",
    "\n",
    "        for i in range(len(arr)):\n",
    "            woo(i)\n",
    "\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJumps(self, arr: List[int], d: int) -> int:\n",
    "        n = len(arr)\n",
    "        rec = [-1]*n\n",
    "\n",
    "        def dfs(x):\n",
    "            # dfs(x)表示从x下标能够到达的下标数量\n",
    "            if rec[x]!=-1:\n",
    "                return rec[x]\n",
    "            res = 1\n",
    "            j = x-1\n",
    "            while j>=0 and j>=x-d and arr[j]<arr[x]:\n",
    "                res = max(res, 1+dfs(j))\n",
    "                j-=1\n",
    "            j = x+1\n",
    "            while j<n and j<=x+d and arr[j]<arr[x]:\n",
    "                res = max(res, 1+dfs(j))\n",
    "                j+=1\n",
    "            rec[x] = res\n",
    "            return res\n",
    "        \n",
    "        for i in range(n):\n",
    "            if rec[i]==-1:\n",
    "                dfs(i)\n",
    "\n",
    "        return max(rec)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJumps(self, arr: List[int], d: int) -> int:\n",
    "        dp = [0]*len(arr)\n",
    "\n",
    "        def woo(i):\n",
    "            if dp[i]>0:\n",
    "                return dp[i]\n",
    "\n",
    "            dp[i] = 1\n",
    "            for di in (-1, 1):\n",
    "                for j in range(i+di, i+di*d+di, di):\n",
    "                    if j<0 or j>=len(arr) or arr[j]>=arr[i]:\n",
    "                        break\n",
    "\n",
    "                    dp[i] = max(dp[i], woo(j)+1)\n",
    "\n",
    "            return dp[i]\n",
    "\n",
    "        for i in range(len(arr)):\n",
    "            woo(i)\n",
    "\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJumps(self, arr: List[int], d: int) -> int:\n",
    "        n = len(arr)\n",
    "        left, right = [], []\n",
    "        for i in range(n):\n",
    "            lMax, point = -1, set()\n",
    "            for j in range(i + 1, n):\n",
    "                if j - i > d:\n",
    "                    break\n",
    "                if arr[i] > arr[j]:\n",
    "                    if lMax == -1 or arr[j] > lMax:\n",
    "                        point = set([j])\n",
    "                        lMax = arr[j]\n",
    "                    elif lMax == arr[j]:\n",
    "                        point.add(j)\n",
    "                else:\n",
    "                    break\n",
    "            left.append(point)\n",
    "            rMax, point = -1, set()\n",
    "            for j in range(i-1, -1, -1):\n",
    "                if i - j > d:\n",
    "                    break\n",
    "                if arr[i] > arr[j]:\n",
    "                    if rMax == -1 or rMax < arr[j]:\n",
    "                        rMax = arr[j]\n",
    "                        point = set([j])\n",
    "                    elif rMax == arr[j]:\n",
    "                        point.add(j)\n",
    "                else:\n",
    "                    break\n",
    "            right.append(point)\n",
    "        self.left, self.right = left, right\n",
    "        #print(left)\n",
    "        #print(right)\n",
    "        self.depth = {}\n",
    "        res = 1\n",
    "        for start in range(n):\n",
    "            d = self.dfs(start)\n",
    "            res = max(res, d)\n",
    "        return res\n",
    "    \n",
    "    def dfs(self, current):\n",
    "        if current in self.depth:\n",
    "            return self.depth[current]\n",
    "        d = 0\n",
    "        for i in self.left[current]:\n",
    "            d = max(d, self.dfs(i))\n",
    "        for i in self.right[current]:\n",
    "            d = max(d, self.dfs(i))\n",
    "        d += 1\n",
    "        self.depth[current] = d\n",
    "        return d\n",
    "\n",
    "        #走到能到的最高位置，因为如果路上其他位置可以去的更远，这一位置一定能到那里。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJumps(self, arr: List[int], d: int) -> int:\n",
    "        n = len(arr)\n",
    "        rec = [-1]*n\n",
    "\n",
    "        def dfs(x):\n",
    "            # dfs(x)表示从x下标能够到达的下标数量\n",
    "            # dfs(x) = 1 + max(dfs(j)) j是从x能够到达的所有下标\n",
    "            if rec[x]!=-1:\n",
    "                return rec[x]\n",
    "            res = 1\n",
    "            j = x-1\n",
    "            while j>=0 and j>=x-d and arr[j]<arr[x]:\n",
    "                res = max(res, 1+dfs(j))\n",
    "                j-=1\n",
    "            j = x+1\n",
    "            while j<n and j<=x+d and arr[j]<arr[x]:\n",
    "                res = max(res, 1+dfs(j))\n",
    "                j+=1\n",
    "            rec[x] = res\n",
    "            return res\n",
    "        \n",
    "        for i in range(n):\n",
    "            if rec[i]==-1:\n",
    "                dfs(i)\n",
    "\n",
    "        return max(rec)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJumps(self, arr: List[int], d: int) -> int:\n",
    "        n = len(arr)\n",
    "        dp = [1] * n  # 初始化dp数组为1\n",
    "        \n",
    "        def dfs(i):\n",
    "            if dp[i] != 1:\n",
    "                return dp[i]\n",
    "            \n",
    "            # 向左跳跃\n",
    "            for j in range(i - 1, i - d - 1, -1):\n",
    "                if j < 0 or arr[j] >= arr[i]:\n",
    "                    break\n",
    "                dp[i] = max(dp[i], dfs(j) + 1)\n",
    "            \n",
    "            # 向右跳跃\n",
    "            for j in range(i + 1, i + d + 1):\n",
    "                if j >= n or arr[j] >= arr[i]:\n",
    "                    break\n",
    "                dp[i] = max(dp[i], dfs(j) + 1)\n",
    "            \n",
    "            return dp[i]\n",
    "        \n",
    "        for i in range(n):\n",
    "            dfs(i)\n",
    "        \n",
    "        return max(dp) if dp else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJumps(self, arr: List[int], d: int) -> int:\n",
    "        n = len(arr)\n",
    "        dp = [1] * n\n",
    "\n",
    "        def jump(i):\n",
    "            if dp[i] > 1:\n",
    "                return dp[i]\n",
    "            for j in range(i + 1, min(i + d + 1, n)):\n",
    "                if arr[i] > arr[j]:\n",
    "                    dp[i] = max(dp[i], 1 + jump(j))\n",
    "                else:\n",
    "                    break\n",
    "            for j in range(i - 1, max(i - d - 1, -1), -1):\n",
    "                if arr[i] > arr[j]:\n",
    "                    dp[i] = max(dp[i], 1 + jump(j))\n",
    "                else:\n",
    "                    break\n",
    "            return dp[i]\n",
    "\n",
    "        for i in range(n):\n",
    "            jump(i)\n",
    "\n",
    "        return max(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJumps(self, arr: List[int], d: int) -> int:\n",
    "        n = len(arr)\n",
    "        dp = [1] * n\n",
    "\n",
    "        def dfs(i):\n",
    "            if dp[i] > 1:\n",
    "                return dp[i]\n",
    "\n",
    "            for j in range(1, d + 1):\n",
    "                if i + j < n and arr[i + j] < arr[i]:\n",
    "                    dp[i] = max(dp[i], dfs(i + j) + 1)\n",
    "                else:\n",
    "                    break\n",
    "\n",
    "            for j in range(1, d + 1):\n",
    "                if i - j >= 0 and arr[i - j] < arr[i]:\n",
    "                    dp[i] = max(dp[i], dfs(i - j) + 1)\n",
    "                else:\n",
    "                    break\n",
    "\n",
    "            return dp[i]\n",
    "\n",
    "        for i in range(n):\n",
    "            dfs(i)\n",
    "\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJumps(self, arr: List[int], d: int) -> int:\n",
    "        n=len(arr)\n",
    "        rem=[0]*n\n",
    "        def dfs(x):\n",
    "            if rem[x]!=0:\n",
    "                return rem[x]\n",
    "            ret=0\n",
    "            for i in range(x+1,x+d+1):\n",
    "                if 0<=i<n:\n",
    "                    if arr[x]>arr[i]:\n",
    "                        ret=max(ret,dfs(i))\n",
    "                    else:\n",
    "                        break\n",
    "            for i in range(x-1,x-d-1,-1):\n",
    "                if 0<=i<n:\n",
    "                    if arr[x]>arr[i]:\n",
    "                        ret=max(ret,dfs(i))\n",
    "                    else:\n",
    "                        break\n",
    "            rem[x]=ret+1\n",
    "            return ret+1\n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            ans=max(ans,dfs(i))\n",
    "        print(rem)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJumps(self, arr: List[int], d: int) -> int:\n",
    "        n = len(arr)\n",
    "        @cache\n",
    "        def dfs(x):\n",
    "            res = 0\n",
    "            for i in range(1, d + 1):\n",
    "                if x - i < 0 or arr[x - i] >= arr[x]:\n",
    "                    break\n",
    "                res = max(res, dfs(x - i) + 1)\n",
    "            for i in range(1, d + 1):\n",
    "                if x + i > n - 1 or arr[x + i] >= arr[x]:\n",
    "                    break\n",
    "                res = max(res, dfs(x + i) + 1)\n",
    "            return res\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            ans = max(ans, dfs(i) + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJumps(self, arr: List[int], d: int) -> int:\n",
    "        n = len(arr)\n",
    "\n",
    "        @cache\n",
    "        def dp(i):\n",
    "            ans = 1\n",
    "            for j in range(i + 1, i + d + 1):\n",
    "                if j < n and arr[j] < arr[i]:\n",
    "                    ans = max(ans, dp(j) + 1)\n",
    "                else:\n",
    "                    break\n",
    "            for j in range(i - 1, i - d - 1, -1):\n",
    "                if 0 <= j and arr[j] < arr[i]:\n",
    "                    ans = max(ans, dp(j) + 1)\n",
    "                else:\n",
    "                    break\n",
    "            return ans\n",
    "\n",
    "        return max(map(dp, range(n)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJumps(self, arr: List[int], d: int) -> int:\n",
    "        n = len(arr)\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            res = 0\n",
    "            for j in range(i-1, i-d-1, -1):\n",
    "                if 0 <= j < n and arr[j] < arr[i]:\n",
    "                    res = max(res, dfs(j) + 1)\n",
    "                else:\n",
    "                    break\n",
    "            for j in range(i+1, i+d+1):\n",
    "                if 0 <= j < n and arr[j] < arr[i]:\n",
    "                    res = max(res, dfs(j) + 1) \n",
    "                else:\n",
    "                    break\n",
    "            return res\n",
    "        # for i in range(n):\n",
    "        #     print(i, dfs(i))\n",
    "        return max(dfs(i) for i in range(n)) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJumps(self, arr: List[int], d: int) -> int:\n",
    "        n = len(arr)\n",
    "        @cache\n",
    "        def fun(now):\n",
    "            res = 1\n",
    "            for nex in range(d):\n",
    "                if 0 <= now+nex+1 < n and arr[now+nex+1] < arr[now]:\n",
    "                    res = max(res, 1+fun(now+nex+1))\n",
    "                else:\n",
    "                    break\n",
    "            for nex in range(d):\n",
    "                if 0 <= now-nex-1 < n and arr[now-nex-1] < arr[now]:\n",
    "                    res = max(res, 1+fun(now-nex-1))\n",
    "                else:\n",
    "                    break\n",
    "            return res\n",
    "        return max(fun(i) for i in range(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJumps(self, arr: List[int], d: int) -> int:\n",
    "        n=len(arr)\n",
    "        @cache\n",
    "        def dfs(pos):\n",
    "            ans=0\n",
    "            maxx=-1\n",
    "            for i in range(pos-1,max(-1,pos-d-1),-1):\n",
    "                maxx=max(maxx,arr[i])\n",
    "                if arr[pos]>maxx:\n",
    "                    ans=max(ans,dfs(i))\n",
    "            maxx=-1\n",
    "            for i in range(pos+1,min(n,pos+d+1)):\n",
    "                maxx=max(maxx,arr[i])\n",
    "                if arr[pos]>maxx:\n",
    "                    ans=max(ans,dfs(i))\n",
    "\n",
    "            return ans+1\n",
    "\n",
    "\n",
    "\n",
    "        # print(dfs(2))\n",
    "        # print([dfs(i) for i in range(n)])\n",
    "        return max([dfs(i) for i in range(n)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJumps(self, arr: List[int], d: int) -> int:\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            res = 1\n",
    "            r,r_limit = i + 1,i + d\n",
    "            l,l_limit = i - 1,i - d\n",
    "            while l >= 0 and l >= l_limit and arr[l] < arr[i]:\n",
    "                res = max(res,dfs(l)+1)\n",
    "                l -= 1\n",
    "            while r < len(arr) and r <= r_limit and arr[r] < arr[i]:\n",
    "                res = max(res,dfs(r)+1)\n",
    "                r += 1\n",
    "            return res\n",
    "        if d == 0:\n",
    "            return 1\n",
    "        res = 1\n",
    "        for i in range(len(arr)):\n",
    "            res = max(res,dfs(i))\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def maxJumps(self, arr: List[int], d: int) -> int:\r\n",
    "        @cache\r\n",
    "        def dfs(i: int) -> int:\r\n",
    "            res = 0 \r\n",
    "            for j in range(1, d + 1):\r\n",
    "                if i - j >= 0 and arr[i - j] < arr[i]:\r\n",
    "                    res = max(res, dfs(i - j))\r\n",
    "                else: break \r\n",
    "            for j in range(1, d + 1):\r\n",
    "                if i + j < len(arr) and arr[i + j] < arr[i]:\r\n",
    "                    res = max(res, dfs(i + j))\r\n",
    "                else: break \r\n",
    "            return res + 1\r\n",
    "        return max(dfs(i) for i in range(len(arr)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJumps(self, arr: List[int], d: int) -> int:\n",
    "        @lru_cache(maxsize=None)\n",
    "        def jump(i):\n",
    "            vis = 0\n",
    "            for x in range(1,d+1):\n",
    "                j = i-x\n",
    "                if j<0 or arr[j]>=arr[i]:\n",
    "                    break\n",
    "                vis = max(vis,jump(j))\n",
    "            for x in range(1,d+1):\n",
    "                j = i+x\n",
    "                if j>=len(arr) or arr[j]>=arr[i]:\n",
    "                    break\n",
    "                vis = max(vis,jump(j))\n",
    "            return vis+1\n",
    "        return max(jump(i) for i in range(len(arr)))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJumps(self, arr: List[int], d: int) -> int:\n",
    "        n = len(arr)\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            ans = 1\n",
    "            minidx, maxidx = max(0, i - d), min(i + d, n - 1)\n",
    "            \n",
    "            left = i - 1\n",
    "            while left >= minidx and arr[left] < arr[i]:\n",
    "                ans = max(ans, dfs(left) + 1)\n",
    "                left -= 1\n",
    "\n",
    "            right = i + 1\n",
    "            while right <= maxidx and arr[right] < arr[i]:\n",
    "                ans = max(ans, dfs(right) + 1)\n",
    "                right += 1\n",
    "\n",
    "            return ans\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            ans = max(ans, dfs(i))\n",
    "\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def maxJumps(self, arr: List[int], d: int) -> int:\r\n",
    "        @cache\r\n",
    "        def dfs(i: int) -> int:\r\n",
    "            res = 0 \r\n",
    "            for j in range(1, d + 1):\r\n",
    "                if i - j >= 0 and arr[i - j] < arr[i]:\r\n",
    "                    res = max(res, dfs(i - j) + 1)\r\n",
    "                else: break \r\n",
    "            for j in range(1, d + 1):\r\n",
    "                if i + j < len(arr) and arr[i + j] < arr[i]:\r\n",
    "                    res = max(res, dfs(i + j) + 1)\r\n",
    "                else: break \r\n",
    "            return res\r\n",
    "        return max(dfs(i) + 1 for i in range(len(arr)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJumps(self, arr: List[int], d: int) -> int:\n",
    "       @cache\n",
    "       def dfs(i: int) -> int:\n",
    "          res = 0\n",
    "          for j in range(i - 1, -1, -1):\n",
    "             if i - j > d or arr[j] >= arr[i]:\n",
    "                break\n",
    "             res = max(res, dfs(j))\n",
    "          for j in range(i + 1, n):\n",
    "             if j - i > d or arr[j] >= arr[i]:\n",
    "                break\n",
    "             res = max(res, dfs(j))\n",
    "          return res + 1\n",
    "       n = len(arr)\n",
    "       return max(dfs(x) for x in range(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJumps(self, arr: List[int], d: int) -> int:\n",
    "        # 先统计每个数字左右的比它小的数量 \n",
    "        # 使用单调栈 or \n",
    "        # 再记忆化 搜索-> 或\n",
    "        st = [[inf, -1]]\n",
    "        n  = len(arr)\n",
    "        left = [0]* n\n",
    "        @cache\n",
    "        def f(x):\n",
    "            t = 0\n",
    "            for i in range(x-1, x-d-1, -1):\n",
    "                if i < 0:break\n",
    "                if arr[i] >= arr[x]:break\n",
    "                t = max(t, f(i))\n",
    "            for i in range(x+1, x+d+1):\n",
    "                if i >= n:break\n",
    "                if arr[i] >= arr[x]:break\n",
    "                t = max(t, f(i))\n",
    "            return t+1\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            ans = max(ans, f(i))\n",
    "        return ans\n",
    "        \n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJumps(self, arr: List[int], d: int) -> int:\n",
    "        @cache\n",
    "        def f(i):\n",
    "            ans = 1\n",
    "            high = -inf \n",
    "            for k in range(i-1, max(0, i-d)-1, -1):\n",
    "                high = max(high, arr[k])\n",
    "                if high >= arr[i]:\n",
    "                    break\n",
    "                if arr[k] < arr[i]:\n",
    "                    ans = max(ans, 1+f(k))\n",
    "                    \n",
    "            high = -inf\n",
    "            for k in range(i+1, min(i+d+1, arr.__len__())):\n",
    "                high = max(high, arr[k])\n",
    "                if high >= arr[i]:\n",
    "                    break\n",
    "                if arr[k] < arr[i]:\n",
    "                    ans = max(ans, 1+f(k))\n",
    "            return ans\n",
    "\n",
    "\n",
    "        return max(f(i) for i in range(0, arr.__len__())) \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJumps(self, arr: List[int], d: int) -> int:\n",
    "        n = len(arr)\n",
    "\n",
    "        @cache\n",
    "        def f(i):\n",
    "            l = max(0, i - d)\n",
    "            r = min(n - 1, i + d)\n",
    "            res = 1\n",
    "            j = i - 1\n",
    "            while j >= l and arr[j] < arr[i]:\n",
    "                res = max(res, f(j) + 1)\n",
    "                j -= 1\n",
    "            j = i + 1\n",
    "            while j <= r and arr[j] < arr[i]:\n",
    "                res = max(res, f(j) + 1)\n",
    "                j += 1\n",
    "            return res\n",
    "\n",
    "        return max(f(i) for i in range(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJumps(self, arr: List[int], d: int) -> int:\n",
    "        n = len(arr)\n",
    "\n",
    "        @cache\n",
    "        def helper(i):\n",
    "            left, right = i, i\n",
    "            for j in range(i - 1, max(0, i - d) - 1, -1):\n",
    "                if arr[j] >= arr[i]:\n",
    "                    break\n",
    "                left = j\n",
    "            \n",
    "            for j in range(i + 1, min(n, i + d + 1)):\n",
    "                if arr[j] >= arr[i]:\n",
    "                    break\n",
    "                right = j\n",
    "            \n",
    "            res = 0\n",
    "            for j in range(left, right + 1):\n",
    "                if i == j:\n",
    "                    continue\n",
    "                res = max(res, helper(j) + 1)\n",
    "            return res\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            ans = max(ans, helper(i))\n",
    "        return ans + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJumps(self, arr: List[int], d: int) -> int:\n",
    "        \n",
    "        @cache\n",
    "        def helper(i):\n",
    "            res = []\n",
    "            for j in range(1, d+1):\n",
    "                if i-j >= 0 and arr[i-j] < arr[i]:\n",
    "                    res.append(helper(i-j)+1)\n",
    "                else:\n",
    "                    break\n",
    "            for j in range(1, d+1):\n",
    "                if i+j < len(arr) and arr[i+j] < arr[i]:\n",
    "                    res.append(helper(i+j)+1)\n",
    "                else:\n",
    "                    break\n",
    "            if len(res) == 0:\n",
    "                return 1\n",
    "            # print(i, max(res))\n",
    "            return max(res)\n",
    "        \n",
    "        res = 0\n",
    "        for i in range(len(arr)):\n",
    "            res = max(helper(i), res)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    记忆化搜索\n",
    "    helper(i) 表示从i出发，在合法跳跃范围内[i - d, i + d]种最多能跳跃的跳数\n",
    "    每计算一个下标跳跃的长度都先计算出在[i - d, i + d]中能跳跃的左边界、右边界，\n",
    "    在左右边界中任选一个非当前站立的下标，继续拆解子问题递归求解\n",
    "    '''\n",
    "    def maxJumps(self, arr: List[int], d: int) -> int:\n",
    "        n = len(arr)\n",
    "\n",
    "        @cache\n",
    "        def helper(i):\n",
    "            left, right = i, i\n",
    "            for j in range(i - 1, max(0, i - d) - 1, -1):\n",
    "                if arr[j] >= arr[i]:\n",
    "                    break\n",
    "                left = j\n",
    "            \n",
    "            for j in range(i + 1, min(n, i + d + 1)):\n",
    "                if arr[j] >= arr[i]:\n",
    "                    break\n",
    "                right = j\n",
    "            \n",
    "            res = 0\n",
    "            for j in range(left, right + 1):\n",
    "                if i == j:\n",
    "                    continue\n",
    "                res = max(res, helper(j) + 1)\n",
    "            return res\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            ans = max(ans, helper(i))\n",
    "        '''\n",
    "        题目中要求经过的节点数，而结果返回的是跳跃数，所以要加一\n",
    "        '''\n",
    "        return ans + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJumps(self, arr: List[int], d: int) -> int:\n",
    "        seen = dict()\n",
    "\n",
    "        def dfs(pos):\n",
    "            if pos in seen:\n",
    "                return\n",
    "            seen[pos] = 1\n",
    "\n",
    "            i = pos - 1\n",
    "            while i >= 0 and pos - i <= d and arr[pos] > arr[i]:\n",
    "                dfs(i)\n",
    "                seen[pos] = max(seen[pos], seen[i] + 1)\n",
    "                i -= 1\n",
    "            i = pos + 1\n",
    "            while i < len(arr) and i - pos <= d and arr[pos] > arr[i]:\n",
    "                dfs(i)\n",
    "                seen[pos] = max(seen[pos], seen[i] + 1)\n",
    "                i += 1\n",
    "\n",
    "        for i in range(len(arr)):\n",
    "            dfs(i)\n",
    "        print(seen)\n",
    "        return max(seen.values())\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJumps(self, arr: List[int], d: int) -> int:\n",
    "        seen=dict()\n",
    "\n",
    "        def dfs(pos):\n",
    "            if pos in seen:\n",
    "                return\n",
    "            seen[pos]=1\n",
    "\n",
    "            i=pos-1\n",
    "            while i>=0 and pos-i<=d and arr[pos]>arr[i]:\n",
    "                dfs(i)\n",
    "                seen[pos]=max(seen[pos],seen[i]+1)\n",
    "                i-=1\n",
    "            i=pos+1\n",
    "            while i<len(arr) and i-pos<=d and arr[pos]>arr[i]:\n",
    "                dfs(i)\n",
    "                seen[pos]=max(seen[pos],seen[i]+1)\n",
    "                i+=1\n",
    "\n",
    "        for i in range(len(arr)):\n",
    "            dfs(i)\n",
    "        print(seen)\n",
    "        return max(seen.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJumps(self, arr: List[int], d: int) -> int:        \n",
    "        seen = dict()\n",
    "        def dfs(pos):\n",
    "            if pos in seen:\n",
    "                return\n",
    "            seen[pos] = 1\n",
    "\n",
    "            i = pos -1\n",
    "            while i>=0 and pos-i <= d and arr[i]<arr[pos]:\n",
    "                dfs(i)\n",
    "                seen[pos] = max(seen[pos],seen[i]+1)\n",
    "                i-=1\n",
    "\n",
    "            i = pos +1\n",
    "            while i<len(arr) and i-pos<=d and arr[i] < arr[pos]:\n",
    "                dfs(i)\n",
    "                seen[pos] = max(seen[pos],seen[i]+1)\n",
    "                i+=1\n",
    "        for i in range(len(arr)):\n",
    "            dfs(i)\n",
    "        return max(seen.values())\n",
    "\n",
    "            \n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJumps(self, arr: List[int], d: int) -> int:        \n",
    "        seen = dict()\n",
    "        def dfs(pos):\n",
    "            if pos in seen:\n",
    "                return\n",
    "            seen[pos] = 1\n",
    "\n",
    "            i = pos -1\n",
    "            while i>=0 and pos-i <= d and arr[i]<arr[pos]:\n",
    "                dfs(i)\n",
    "                seen[pos] = max(seen[pos],seen[i]+1)\n",
    "                i-=1\n",
    "\n",
    "            i = pos +1\n",
    "            while i<len(arr) and i-pos<=d and arr[i] < arr[pos]:\n",
    "                dfs(i)\n",
    "                seen[pos] = max(seen[pos],seen[i]+1)\n",
    "                i+=1\n",
    "        for i in range(len(arr)):\n",
    "            dfs(i)\n",
    "        return max(seen.values())\n",
    "\n",
    "            \n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJumps(self, arr: List[int], d: int) -> int:\n",
    "        seen = dict()\n",
    "        n = len(arr)\n",
    "        def dfs(pos):\n",
    "\n",
    "            if pos in seen:\n",
    "                return\n",
    "\n",
    "            seen[pos] = 1\n",
    "\n",
    "            i = pos - 1\n",
    "            while i >= 0 and pos - i <= d and arr[pos] > arr[i]:\n",
    "                dfs(i)\n",
    "                seen[pos] = max(seen[pos], seen[i] + 1)\n",
    "                i -= 1\n",
    "            i = pos + 1\n",
    "\n",
    "            while i < n and i - pos <= d and arr[pos] > arr[i]:\n",
    "                dfs(i)\n",
    "                seen[pos] = max(seen[pos], seen[i] + 1)\n",
    "                i += 1\n",
    "            \n",
    "        \n",
    "        for i in range(n):\n",
    "            dfs(i)\n",
    "        \n",
    "        return max(seen.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJumps(self, arr: List[int], d: int) -> int:\n",
    "\n",
    "        seen = dict()\n",
    "\n",
    "        def dfs(pos):\n",
    "            if pos in seen:\n",
    "                return\n",
    "            seen[pos] = 1\n",
    "\n",
    "            i = pos - 1\n",
    "            while i >= 0 and pos-i <= d and arr[pos] > arr[i]:\n",
    "                dfs(i)\n",
    "                seen[pos] = max(seen[pos], seen[i]+1)\n",
    "                i -= 1\n",
    "            i = pos + 1\n",
    "            while i < len(arr) and i - pos <= d and arr[pos] > arr[i]:\n",
    "                dfs(i)\n",
    "                seen[pos] = max(seen[pos],seen[i]+1)\n",
    "                i+=1\n",
    "            \n",
    "        for i in range(len(arr)):\n",
    "            dfs(i)\n",
    "        \n",
    "        return max(seen.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJumps(self, arr: List[int], d: int) -> int:\n",
    "        seen = {}\n",
    "\n",
    "        def dfs(i):\n",
    "            # 表示从下标i开始进行跳跃最多能跳多少个下标\n",
    "            if i in seen:\n",
    "                return \n",
    "            seen[i] = 1\n",
    "            # i-d <= j <= i+d\n",
    "\n",
    "            j = i - 1\n",
    "            while j >= 0 and i - j <= d and arr[i] > arr[j]:\n",
    "                dfs(j)\n",
    "                seen[i] = max(seen[i], seen[j] + 1)\n",
    "                j -= 1\n",
    "\n",
    "            j = i+1\n",
    "            while j < len(arr) and j - i <= d and arr[i] > arr[j]:\n",
    "                dfs(j)\n",
    "                seen[i] = max(seen[i], seen[j] + 1)\n",
    "                j += 1\n",
    "            \n",
    "        # 枚举每个下标作为起点\n",
    "        for i in range(len(arr)):\n",
    "            dfs(i)\n",
    "        return max(seen.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJumps(self, arr: List[int], d: int) -> int:\n",
    "        seen = dict()\n",
    "        def dfs(pos):\n",
    "            if pos in seen:\n",
    "                 return \n",
    "            seen[pos] = 1\n",
    "            i = pos-1\n",
    "            while i>=0 and pos-i<=d and arr[pos] > arr[i]:\n",
    "                dfs(i)\n",
    "                seen[pos] = max(seen[pos],seen[i]+1)\n",
    "                i -= 1\n",
    "            i = pos + 1\n",
    "            while i<len(arr) and i-pos<=d and arr[pos]>arr[i]:\n",
    "                dfs(i)\n",
    "                seen[pos] = max(seen[pos],seen[i]+1)\n",
    "                i += 1\n",
    "        for i in range(len(arr)):\n",
    "            dfs(i)\n",
    "        return max(seen.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJumps(self, arr: List[int], d: int) -> int:\n",
    "        seen = dict()\n",
    "\n",
    "        def dfs(pos):\n",
    "            if pos in seen:\n",
    "                return seen[pos]\n",
    "            seen[pos] = 1\n",
    "\n",
    "            i = pos - 1\n",
    "            while i >= 0 and pos - i <= d and arr[pos] > arr[i]:\n",
    "                seen[pos] = max(1+dfs(i),seen[pos] )\n",
    "                i -= 1\n",
    "\n",
    "            i = pos + 1\n",
    "            while i < len(arr)  and i - pos <= d and arr[pos] > arr[i]:\n",
    "                seen[pos] = max(1+dfs(i),seen[pos] )\n",
    "                i += 1 \n",
    "            return seen[pos]\n",
    "        \n",
    "\n",
    "        n = len(arr)\n",
    "        return max(dfs(i) for i in range(n))\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJumps(self, arr: List[int], d: int) -> int:\n",
    "        memo = {}\n",
    "\n",
    "        def dfs(pos):\n",
    "            if (memo.get(pos) != None):\n",
    "                return\n",
    "            memo[pos] = 1\n",
    "            i = pos - 1\n",
    "            while (i >= 0 and i + d >= pos and arr[pos] > arr[i]):\n",
    "                dfs(i)\n",
    "                memo[pos] = max(memo[pos], memo[i]+1)\n",
    "                i -= 1\n",
    "            i = pos + 1\n",
    "            while (i < len(arr) and i - d <= pos and arr[pos] > arr[i]):\n",
    "                dfs(i)\n",
    "                memo[pos] = max(memo[pos], memo[i]+1)\n",
    "                i += 1\n",
    "        \n",
    "        for i in range(len(arr)):\n",
    "            dfs(i)\n",
    "        \n",
    "        return max(memo.values())\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJumps(self, arr: List[int], d: int) -> int:\n",
    "\n",
    "\n",
    "        seen = dict()\n",
    "        n = len(arr)\n",
    "        def dfs(pos):\n",
    "\n",
    "            if pos in seen:\n",
    "                return\n",
    "\n",
    "            seen[pos] = 1\n",
    "\n",
    "            i = pos - 1\n",
    "            while i >= 0 and pos - i <= d and arr[pos] > arr[i]:\n",
    "                dfs(i)\n",
    "                seen[pos] = max(seen[pos], seen[i] + 1)\n",
    "                i -= 1\n",
    "            i = pos + 1\n",
    "\n",
    "            while i < n and i - pos <= d and arr[pos] > arr[i]:\n",
    "                dfs(i)\n",
    "                seen[pos] = max(seen[pos], seen[i] + 1)\n",
    "                i += 1\n",
    "            \n",
    "        \n",
    "        for i in range(n):\n",
    "            dfs(i)\n",
    "        \n",
    "        return max(seen.values())\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJumps(self, arr: List[int], d: int) -> int:\n",
    "        seen = dict()\n",
    "        def dfs(pos):\n",
    "            if pos in seen:\n",
    "                return \n",
    "            seen[pos] = 1\n",
    "            i = pos - 1  # 表示从pos处跳往i处，左面，且是连续一片\n",
    "            while i >= 0 and pos - i <= d and arr[pos] > arr[i]:\n",
    "                dfs(i)\n",
    "                seen[pos] = max(seen[pos], seen[i] + 1)\n",
    "                i -= 1\n",
    "            i = pos + 1  # 表示从pos处跳往i处，右面，且是连续一片\n",
    "            while i < len(arr) and i - pos <= d and arr[pos] > arr[i]:\n",
    "                dfs(i)\n",
    "                seen[pos] = max(seen[pos], seen[i] + 1)\n",
    "                i += 1\n",
    "        for i in range(len(arr)):\n",
    "            dfs(i)\n",
    "        return max(seen.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJumps(self, arr: List[int], d: int) -> int:\n",
    "        \"\"\"\n",
    "        从位置i开始, 下一步可以跳到j, j的范围是[i-d, i+d], 且要求 0<=j<n, arr[j]<arr[i]\n",
    "        dp[i] = max(dp[j]) + 1, 在[i-d, i+d]内找到能跳最多步数的j\n",
    "        从i开始往左往右搜索, 如果j位置能跳到的步数在记忆中,直接用表中记录, 否则再DFS(j)\n",
    "        \"\"\"\n",
    "        def dfs(i):\n",
    "            if i in m:\n",
    "                return\n",
    "\n",
    "            # 将idx位置能跳的最大步数存入记忆表\n",
    "            m[i] = 1\n",
    "            # 往左\n",
    "            for j in range(i-1, max(-1, i-d-1), -1):\n",
    "                if arr[j] >= arr[i]:\n",
    "                    break\n",
    "                dfs(j)\n",
    "                m[i] = max(m[i], 1 + m[j])\n",
    "            # 往右\n",
    "            for j in range(i+1, min(n, i+d+1)):\n",
    "                if arr[j] >= arr[i]:\n",
    "                    break\n",
    "                dfs(j)\n",
    "                m[i] = max(m[i], 1 + m[j])\n",
    "\n",
    "        m = {}  # {index: max jumps}\n",
    "        n = len(arr)\n",
    "        for i in range(n):\n",
    "            dfs(i)\n",
    "        # print(m)\n",
    "        return max(m.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJumps(self, arr: List[int], d: int) -> int:\n",
    "        \"\"\"\n",
    "        从位置i开始, 下一步可以跳到j, j的范围是[i-d, i+d], 且要求 0<=j<n, arr[j]<arr[i]\n",
    "        dp[i] = max(dp[j]) + 1, 在[i-d, i+d]内找到能跳最多步数的j\n",
    "        从i开始往左往右搜索, 如果j位置能跳到的步数在记忆中,直接用表中记录, 否则再DFS(j)\n",
    "        \"\"\"\n",
    "        def dfs(i):\n",
    "            if i in m:\n",
    "                return\n",
    "\n",
    "            # 将idx位置能跳的最大步数存入记忆表\n",
    "            m[i] = 1\n",
    "            # 往左\n",
    "            for j in range(i-1, max(-1, i-d-1), -1):\n",
    "                if arr[j] >= arr[i]:\n",
    "                    break\n",
    "                dfs(j)\n",
    "                m[i] = max(m[i], 1 + m[j])\n",
    "            # 往右\n",
    "            for j in range(i+1, min(n, i+d+1)):\n",
    "                if arr[j] >= arr[i]:\n",
    "                    break\n",
    "                dfs(j)\n",
    "                m[i] = max(m[i], 1 + m[j])\n",
    "\n",
    "        m = {}  # {index: max jumps}\n",
    "        n = len(arr)\n",
    "        for i in range(n):\n",
    "            dfs(i)\n",
    "        # print(m)\n",
    "        return max(m.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJumps(self, arr: List[int], d: int) -> int:\n",
    "        memo = {}\n",
    "        n = len(arr)\n",
    "        def dfs(i):\n",
    "            if i in memo: return \n",
    "            memo[i] = 1\n",
    "            x = 1\n",
    "            while x <= d and i + x < n and arr[i] > arr[i+x]:\n",
    "                dfs(i+x)\n",
    "                memo[i] = max(memo[i], memo[i+x] + 1)\n",
    "                x += 1\n",
    "            x = 1\n",
    "            while x <= d and i - x >= 0 and arr[i] > arr[i-x]:\n",
    "                dfs(i-x)\n",
    "                memo[i] = max(memo[i], memo[i-x] + 1)\n",
    "                x += 1\n",
    "        for i in range(n):dfs(i)\n",
    "        return max(memo.values())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def maxJumps(self, arr: List[int], d: int) -> int:\n",
    "        dic={}\n",
    "        n=len(arr)\n",
    "        def dfs(cur):\n",
    "            if cur in dic:\n",
    "                return dic[cur]\n",
    "            \n",
    "            dic[cur]=1\n",
    "\n",
    "            for t in range(1,d+1):\n",
    "                if t+cur < n and arr[t+cur] < arr[cur]:\n",
    "                    dic[cur]=max(1+dfs(t+cur),dic[cur])\n",
    "                else:\n",
    "                    break\n",
    "\n",
    "            for t in range(1,d+1):\n",
    "                if cur-t >=0 and arr[cur-t] < arr[cur]:\n",
    "                    dic[cur]=max(dic[cur], 1+dfs(cur-t))\n",
    "                else:\n",
    "                    break\n",
    "\n",
    "            return dic[cur]\n",
    "        res=1\n",
    "        for i in range(n):\n",
    "            res=max(res,dfs(i))\n",
    "        return res\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJumps(self, arr: List[int], d: int) -> int:\n",
    "        vis = dict()\n",
    "        n = len(arr)\n",
    "\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            minidx, maxidx = max(0, i - d), min(i+d, n-1)\n",
    "            vis[i] = 1\n",
    "\n",
    "            j = i - 1\n",
    "            while j >= minidx and arr[j] < arr[i]:\n",
    "                dfs(j)\n",
    "                vis[i] = max(vis[i], vis[j] + 1)\n",
    "                j -= 1\n",
    "            \n",
    "            j = i + 1\n",
    "            while j <= maxidx and arr[j] < arr[i]:\n",
    "                dfs(j)\n",
    "                vis[i] = max(vis[i], vis[j] + 1)\n",
    "                j += 1\n",
    "        \n",
    "        for i in range(n):\n",
    "            dfs(i)\n",
    "        \n",
    "        return max(vis.values())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJumps(self, arr: List[int], d: int) -> int:\n",
    "        n = len(arr)\n",
    "        f = dict()\n",
    "\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            minidx, maxidx = max(0, i - d), min(i + d, n-1)\n",
    "            f[i] = 1\n",
    "\n",
    "            left = i - 1\n",
    "            while left >= minidx and arr[left] < arr[i]:\n",
    "                dfs(left)\n",
    "                f[i] = max(f[i], f[left] + 1)\n",
    "                left -= 1\n",
    "            \n",
    "            right = i + 1\n",
    "            while right <= maxidx and arr[right] < arr[i]:\n",
    "                dfs(right)\n",
    "                f[i] = max(f[i], f[right] + 1)\n",
    "                right += 1\n",
    "        \n",
    "        for i in range(n):\n",
    "            dfs(i)\n",
    "\n",
    "        return max(f.values())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxJumps(self, arr: List[int], d: int) -> int:\n",
    "        pathdic = defaultdict(list)\n",
    "        n = len(arr)\n",
    "        if n<=1: return n\n",
    "        indegrees = [0]*n\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n):\n",
    "                if arr[j]<arr[i] and j-i<=d:\n",
    "                    pathdic[i].append(j)\n",
    "                    indegrees[j] += 1\n",
    "                else:\n",
    "                    break\n",
    "            for j in range(i-1, -1, -1):\n",
    "                if arr[j]<arr[i] and i-j<=d:\n",
    "                    pathdic[i].append(j)\n",
    "                    indegrees[j] += 1\n",
    "                else:\n",
    "                    break\n",
    "        # 拓扑排序\n",
    "        queue = Deque()\n",
    "        for i,degree in enumerate(indegrees):\n",
    "            if degree == 0:\n",
    "                queue.append((i,1))\n",
    "        ans = 1\n",
    "        while queue:\n",
    "            node, level = queue.popleft()\n",
    "            for nx_node in pathdic[node]:\n",
    "                ans = max(ans, level+1)\n",
    "                indegrees[nx_node] -= 1\n",
    "                if indegrees[nx_node] == 0:\n",
    "                    queue.append((nx_node, level+1))\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
